package algorithm.graph;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class ShortestPath {

    private Graph graph;

    private boolean visited[];

    private int[] from;

    private int[] ord;

    public ShortestPath(Graph graph,int s){
        this.graph = graph;
        this.visited = new boolean[graph.V()];
        this.from = new int[graph.V()];
        this.ord = new int[graph.V()];
        for (int i = 0; i < graph.V(); i++) {
            visited[i] = false;
            from[i] = -1;
            ord[i] = -1;
        }
        //进行广度优先遍历

        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(s);
        visited[s]=true;
        ord[s]=0;
        while (!stack.isEmpty()){
            Integer pop = stack.pop();
            Iterator<Integer> iterator = graph.iterator(pop);
            while (iterator.hasNext()){
                Integer value = iterator.next();
                if (!visited[value]){
                    stack.push(value);
                    visited[value]=true;
                    from[value]=pop;
                    ord[value]=ord[pop]+1;
                }
            }
        }
    }
    boolean hasPath(int w) {
        return visited[w];
    }

    List<Integer> path(int w) {
        LinkedList<Integer> list = new LinkedList<>();
        int p = w;
        while (p != -1) {
            list.addFirst(p);
            p = from[p];
        }
        return list;
    }


    void showPath(int w) {
        List<Integer> path = path(w);
        for (Integer integer : path) {
            System.out.print(integer);
            System.out.print("->");
        }
    }

    // 测试无权图最短路径算法
    public static void main(String[] args) {

        String filename = "testG.txt";
        Graph g =  ReadGraph.readGraph(SparseGraph.class, filename);
        g.show();
        System.out.println();

        // 比较使用深度优先遍历和广度优先遍历获得路径的不同
        // 广度优先遍历获得的是无权图的最短路径
        Path dfs = new Path(g,0);
        System.out.print("DFS : ");
        dfs.showPath(6);

        ShortestPath bfs = new ShortestPath(g,0);
        System.out.print("BFS : ");
        bfs.showPath(6);
    }
}
